package javaInterview;
// import java.util.*;

public class ClimbStairs {

    // 方法1：动态规划（空间优化版）- 最优解
    // 时间复杂度：O(n)，空间复杂度：O(1)
    public static int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 只需要保存前两个状态即可
        int prev2 = 1;  // dp[i-2]
        int prev1 = 2;  // dp[i-1]
        int current = 0;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // 方法2：动态规划（数组版）
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public static int climbStairsDP(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    // 方法3：递归+记忆化搜索
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public static int climbStairsMemo(int n) {
        int[] memo = new int[n + 1];
        return helper(n, memo);
    }
    
    private static int helper(int n, int[] memo) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (memo[n] > 0) return memo[n];
        
        memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
        return memo[n];
    }
}

